package com.zup.algorithm.sort;

import com.zup.algorithm.util.SortUtils;

import java.util.Arrays;

/**
 * 说明：选择排序
 *
 * @author Created by xujinyan on 2018/5/14.
 */
public class SelectSort {
    public static void sort(int[] arr) {
        // 需要排序的元素下标
        for (int i=0; i<arr.length; i++) {
            int minIndex = i;
            // 选出最小值
            for (int j=i; j<arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            // 进行交换
            SortUtils.swap(arr, i, minIndex);
        }
    }

    public static void sortImprove(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        // 需要排序的元素下标
        while (left < right) {
            int minIndex = left;
            int maxIndex = right;
            // 寻找最小值和最大值
            for (int i=left; i<right; i++) {
                if (arr[minIndex] > arr[i]) {
                    minIndex = i;
                }
                if (arr[maxIndex] < arr[i]) {
                    maxIndex = i;
                }
            }
            SortUtils.swap(arr, right, maxIndex);
            // 如果最右边的元素刚好是最小值，因为刚刚最右边的元素同maxIndex交换过，那么就得更新minIndex
            if (minIndex == right) {
                minIndex = maxIndex;
            }
            SortUtils.swap(arr, left, minIndex);

            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] arr = SortUtils.generateArr(10, 10);
        SelectSort.sortImprove(arr);
        System.out.println(Arrays.toString(arr));
    }
}
